package com.code.test.dance;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 数组 A 中给定可以使用的 1~9 的数，返回由数组 A 中的元素组成的小于 n 的最大数。
 * <p>
 * 给定一个数 n，如 23121;
 * 给定一组数字 A 如{2.4.9)，
 * 求由 A 中元素组成的、
 * 小于 n 的最大数，如小于 23121 的最大数为 22999
 * <p>
 * https://juejin.cn/post/7345687862531194890
 */
public class MaxDigit {

    static int ans = 0;
    static int count = 0;

    /**
     * 解法：
     * https://blog.csdn.net/qq_42039996/article/details/129792776
     * https://juejin.cn/post/7345687862531194890
     * https://juejin.cn/post/7345070627107242036
     */
    /**
     * 回溯
     * https://juejin.cn/post/7089634465399439367
     */
    public static void main(String[] args) {
        int x = 2533;
        int[] candinates = new int[]{1, 2, 4, 9};
        //数组先排序，小到大
        Arrays.sort(candinates);
        int n = x == 0 ? 0 : 1;
        //复制一份
        int t = x;
        while (t / 10 != 0) {
            n++;
            t /= 10;
        }
        if (n == 0) System.out.println(-1);
        ;
        backtrack(candinates, x, 0, n);
        System.out.println(ans);

    }

    static void backtrack(int[] candinates, int x, int res, int n) {
        //如果变量的数量已经大于 入参的数字数量
        if (count > n) return;
        //如果值小于目标值，把值复制给ans，通过回溯不断测试各个结果值，最终保留最大值
        if (res < x) {
            ans = Math.max(ans, res);
        }

        /**
         * 数组已经排过序，这里是要计算最近的，所以从后往前
         */
        for (int i = candinates.length - 1; i >= 0; i--) {
            res = res * 10 + candinates[i];
            count++;
            backtrack(candinates, x, res, n);
            count--;
            //还原
            res = (res - candinates[i]) / 10;
        }
    }

}
